//class Solution {
//public:
//    int hash1[128] = { 0 }, hash2[128] = { 0 };
//    string minWindow(string s, string t) {
//        for (auto ch : t)
//            hash2[ch]++;
//        int m = t.size();
//        int pos = 0, len = INT_MAX;
//        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
//        {
//            char in = s[right];
//            ++hash1[in];
//            if (hash2[in] && hash1[in] <= hash2[in])
//                count++;
//            while (count >= m)
//            {
//                if (right - left + 1 < len)
//                {
//                    pos = left;
//                    len = right - left + 1;
//                }
//                char out = s[left++];
//                hash1[out]--;
//                if (hash2[out] && hash1[out] < hash2[out])
//                    count--;
//            }
//        }
//        return len == INT_MAX ? "" : s.substr(pos, len);
//    }
//};




class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string, int>hash2;
        for (auto& str : words)
            hash2[str]++;
        int n = words.size(), len = words[0].size();
        for (int i = 0; i < len; i++)
        {
            unordered_map<string, int> hash1;
            for (int left = i, right = i, count = 0; right + len <= s.size(); right += len)
            {
                string in = s.substr(right, len);
                hash1[in]++;
                if (hash2[in] && hash1[in] <= hash2[in]) count++;
                if (right - left + 1 > n * len)
                {
                    string out = s.substr(left, len);
                    hash1[out]--;
                    if (hash2[out] && hash1[out] < hash2[out])
                        count--;
                    left += len;
                }
                if (count == n)
                    ret.push_back(left);
            }
        }
        return ret;
    }
};